package a2_linkedlist.singlelinkedlist;
/**
 * 带头单链表
 */
public class SingleLinkedListWithHead {
    //表示当前链表中元素的个数
    private int size;
    //创建虚拟头节点
    private Node dummyHead = new Node(-1);

    /****  添加  *********************/
    //索引插入
    public void addIndex(int index,int val){
        //判断index合法性
        if(index<0 || index>size){
            System.err.println("add index illegal!");
            return;
        }
        //此时的插入就不可能是头插
        Node node = new Node(val);
        //找到插入位置的前驱
        Node prev = dummyHead;
        for(int i=0;i<index;i++){
            //因为链表的头部有个虚拟节点，所以要走index步才行
            prev = prev.next;
        }
        //此时prev指向待插位置的前驱
        node.next = prev.next;
        prev.next = node;
        size++;
    }
    //头插法
    public void addFirst(int val){
        addIndex(0,val);
    }
    //尾插法
    public void addLast(int val){
        addIndex(size,val);
    }

    /****  查找  *********************/
    //返回索引处value的值
    public int get(int index){
        if(rangeCheck(index)){
            Node node = dummyHead.next;
            for(int i=0;i<index;i++){
                node = node.next;
            }
            return node.val;
        }else{
            System.err.println("get index illegal!");
            return -1;
        }
    }
    //判断链表中是否有value这个数据
    public boolean contains(int val){
        for(Node temp=dummyHead.next;temp!=null;temp=temp.next){
            if(temp.val == val)
                return true;
        }
        return false;
    }

    /****  修改  *********************/
    //将单链表中索引为index的元素修改，并返回修改前的值
    public int set(int index,int val){
        if(rangeCheck(index)){
            Node node = dummyHead.next;
            for(int i=0;i<index;i++){
                node = node.next;
            }
            int old = node.val;
            node.val = val;
            return old;
        }else{
            System.err.println("set index illegal!");
            return -1;
        }
    }

    /****  删除  *********************/
    public void removeIndex(int index){
        if(rangeCheck(index)){
            Node prev = dummyHead;
            for(int i=0;i<index;i++){
                prev = prev.next;
            }
            Node cur = prev.next;
            prev.next = cur.next;
            cur.next = null;
            size--;
        }else{
            System.err.println("remove index illegal!");
        }
    }
    //删除第一个value
    public void removeOnceValue(int val){
        Node prev = dummyHead;
        while(prev.next!=null){
            if(prev.next.val == val){
                Node cur = prev.next;
                prev.next = cur.next;
                cur.next = null;
                size--;
                return;
            }
            prev = prev.next;
        }
    }
    //删除所有的value
    public void removeAllValue(int val){
        Node prev = dummyHead;
        while(prev.next!=null){
            if(prev.next.val == val){
                Node cur = prev.next;
                prev.next = cur.next;
                cur.next = null;
                size--;
            }else{
                prev = prev.next;
            }
        }
    }
    //清空链表
    public void clear(){
        dummyHead.next = null;
        size = 0;
    }

    //打印
    public String toString(){
        String str = "";
        Node temp = dummyHead.next;
        while(temp!=null){
            str += temp.val;
            str += " -> ";
            temp = temp.next;
        }
        str += "NULL";
        return str;
    }
    //判断index合法性
    private boolean rangeCheck(int index){
        if(index<0 || index>=size)
            return false;
        else
            return true;
    }
    //返回链表长度
    public int size(){
        return this.size;
    }
}
